from typing import *


class Solution:

    def insert(self, intervals: List[List[int]],
               newInterval: List[int]) -> List[List[int]]:
        ans = []
        n, i = len(intervals), 0
        while i < n and intervals[i][1] < newInterval[0]:
            ans.append(intervals[i])
            i += 1
        if i < n:
            l, r = min(newInterval[0], intervals[i][0]), newInterval[1]
            while i < n and intervals[i][0] <= newInterval[1]:
                r = max(r, intervals[i][1])
                i += 1
            ans.append([l, r])
        else:
            ans.append(newInterval)
        while i < n:
            ans.append(intervals[i])
            i += 1
        return ans